package HuffmanTree;

/**
 * This class implements a single node of a binary tree.  It is a
 * recursive structure.  Relationships between nodes are 
 * doubly linked, with parent and child references.  Many characteristics
 * of trees may be detected with static methods.
 *
 * @param <E> clase genérica
 * @version $Id: BinaryTree.java 34 2007-08-09 14:43:44Z bailey $
 * @author, 2001 duane a. bailey
 * Modificado por Vinicio Gomez
 * @see structure.BinaryTree
 * @see structure.BinarySearchTree
 */
public class BinaryTree <E>
{
    /**
     * The value associated with this node
     */
    protected Object val; // value associated with node
    /**
     * The parent of this node
     */
    protected BinaryTree parent; // parent of node (or null)
    /**
     * The left child of this node, or EMPTY
     */
    protected BinaryTree left, right; // children of node (or empty)
    /**
     * The unique empty node
     */
    public static final BinaryTree EMPTY = new BinaryTree();

    /**
     * A one-time constructor, for constructing empty trees.
     * @post Private constructor that generates the EMPTY node
     */
    public BinaryTree()
    {
        val = null;
        parent = null; 
        left = this;
        right = this;
    }

    /**
     * Constructs a tree node with no children.  Value of the node
     * is provided by the user
     *
     * @post Returns a tree referencing value with two empty subtrees
     * @param value A (possibly null) value to be referenced by node
     */
    public BinaryTree(Object value)
    {
        val = value;
        parent = null;
        left = right = EMPTY;
    }

    /**
     * Constructs a tree node with no children.  Value of the node
     * and subtrees are provided by the user
     *
     * @post Returns a tree referencing value and two subtrees
     * @param value A (possibly null) value to be referenced by node
     * @param left The subtree to be left subtree of node
     * @param right The subtree to be right subtree of node
     */
    public BinaryTree(Object value, BinaryTree left, BinaryTree right)
    {
        this(value);
        setLeft(left);
        setRight(right);
    }

    /**
     * Get left subtree of current node
     *
     * @post Returns reference to (possibly empty) left subtree
     *
     * @return The left subtree of this node
     */
    public BinaryTree left()
    {
        return left;
    }

    /**
     * Get right subtree of current node
     *
     * @post Returns reference to (possibly empty) right subtree
     * 
     * @return The right subtree of this node
     */
    public BinaryTree right()
    {
        return right;
    }

    /**
     * Get reference to parent of this node
     *
     * @post Returns reference to parent node, or null
     * 
     * @return Reference to parent of this node
     */
    public BinaryTree parent()
    {
        return parent;
    }
    
    /**
     * Update the left subtree of this node.  Parent of the left subtree
     * is updated consistently.  Existing subtree is detached
     *
     * @post Sets left subtree to newLeft
     *       re-parents newLeft
     * 
     * @param newLeft The root of the new left subtree
     */
    public void setLeft(BinaryTree newLeft)
    {
        if (isEmpty()) {
            return;
        }
        if (left.parent() == this) {
            left.setParent(null);
        }
        left = newLeft;
        left.setParent(this);
    }

    /**
     * Update the right subtree of this node.  Parent of the right subtree
     * is updated consistently.  Existing subtree is detached
     *
     * @post Sets left subtree to newRight
     *       re-parents newRight
     * 
     * @param newRight A reference to the new right subtree of this node
     */
    public void setRight(BinaryTree newRight)
    {
        if (isEmpty()) {
            return;
        }
        if (right.parent() == this) {
            right.setParent(null);
        }
        right = newRight;
        right.setParent(this);
    }

    /**
     * Update the parent of this node
     *
     * @post Re-parents this node to parent reference, or null
     *
     * @param newParent A reference to the new parent of this node
     */
    protected void setParent(BinaryTree newParent)
    {
        parent = newParent;
    }

    /**
     * Returns true if tree is empty.
     * @post Returns true iff the tree rooted at node is empty
     * @return True iff tree is empty
     */
    public boolean isEmpty()
    {
        return this == EMPTY;
    }
    
    /**
     * Return whether tree is complete.  A complete tree has minimal height
     * and any holes in tree would appear in last level to right.       
     *
     * @post Returns true iff the tree rooted at node is complete
     * @return True iff the subtree is complete
     */
 

    /**
     * Returns value associated with this node
     *
     * @post Returns value associated with this node
     * 
     * @return The node's value
     */
    public Object value()
    {
        return val;
    }

    /**
     * Set's value associated with this node
     *
     * @post Sets the value associated with this node
     * @param value The new value of this node
     */
    public void setValue(Object value)
    {
        val = value;
    }
}
